home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / prog / graphics / embedding.c < prev    next >
C/C++ Source or Header  |  1994-08-05  |  2KB  |  108 lines
  1. #include <LEDA/graph.h>
  2. #include <LEDA/graph_alg.h>
  3. #include <LEDA/window.h>
  4. #include <LEDA/graph_edit.h>
  5. #include <LEDA/sweep_segments.h>
  6.  
  7. void random_planar_graph(int N, window& W, GRAPH<point,int>& G)
  8. { list<segment> L,L0;
  9.   node v,w;
  10.   edge e;
  11.   W.init(-1000,1000,-1000);
  12.   W.message("random graph (sweeping)");
  13.   forall_nodes(v,G) W.draw_node(G[v]);
  14.   forall_edges(e,G)  
  15.   { v = source(e);
  16.     w = target(e);
  17.     W.draw_edge(G[v],G[w],blue);
  18.    }
  19.  
  20.   while (N--) 
  21.   { double x1 = random(-990,0);
  22.     double y1 = random(-990,900);
  23.     double x2 = random(0,990);
  24.     double y2 = random(-990,900);
  25.     segment s(x1,y1,x2,y2);
  26.     W << s;
  27.     L.append(s);
  28.    }
  29.  
  30.   SWEEP_SEGMENTS(L,L0,G);
  31. }
  32.  
  33.  
  34. main()
  35. {
  36.   window W;
  37.   panel P;
  38.  
  39.   GRAPH<point,int> G;
  40.   node v,w;
  41.   edge e;
  42.  
  43.   int  N = 40;
  44.   int  node_width   = 12;
  45.   int  edge_width   =  1;
  46.   bool random_input = true;
  47.  
  48.   P.bool_item("random input",random_input);
  49.   P.int_item("# segments",N);
  50.   P.int_item("node width",node_width,1,15);
  51.   P.int_item("edge width",edge_width,1,8);
  52.  
  53.  
  54.   for(;;)
  55.   {
  56.     P.open();
  57.     W.set_node_width(node_width);
  58.     W.set_line_width(edge_width);
  59.  
  60.     G.clear();
  61.  
  62.     if (random_input)
  63.      { W.set_node_width(3);
  64.        random_planar_graph(N,W,G);
  65.       }
  66.     else
  67.        graph_edit(W,G,false);
  68.  
  69.   
  70.     W.del_message();
  71.     W.message(string("PLANARITY TEST  N = %d",G.number_of_nodes()));
  72.   
  73.     if ( ! PLANAR(G) )
  74.     { W.acknowledge("Graph is not planar");
  75.       continue;
  76.      }
  77.   
  78.   
  79.      node_array<int> x(G),y(G);
  80.   
  81.   
  82.      W.del_message();
  83.      W.message("STRAIGHT LINE EMBEDDING");
  84.   
  85.      STRAIGHT_LINE_EMBEDDING(G,x,y);
  86.      
  87.      int xmax=0;
  88.   
  89.      forall_nodes(w,G)  
  90.        if (x[w]>xmax) xmax= x[w];
  91.      
  92.      
  93.      W.init(-5,xmax+5,-5);
  94.   
  95.      forall_nodes(v,G) W.draw_node(x[v],2*y[v]);
  96.      forall_edges(e,G)  
  97.      { v = source(e);
  98.        w = target(e);
  99.        W.draw_edge(point(x[v],2*y[v]),point(x[w],2*y[w]),red);
  100.       }
  101.      
  102.       W.read_mouse();
  103.  
  104.     }
  105.      
  106.   return 0;
  107.  }
  108.